package qsort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 功能描述:
 *
 * @author lixiaomeng
 * @date 2018/12/24
 */
public class SortMain {

    public static List<Integer> qSort(List<Integer> list) {

        if (list.size() < 2)
            return list;

        int pivot = list.get(0);
        List<Integer> pivotList = new ArrayList<>();
        List<Integer> before = new ArrayList<>();
        List<Integer> after = new ArrayList<>();
        for (Integer i : list) {
            if (i < pivot) {
                before.add(i);
            } else if (i > pivot){
                after.add(i);
            } else {
                pivotList.add(i);
            }
        }
        before = qSort(before);
        after = qSort(after);
        before.addAll(pivotList);
        before.addAll(after);
        return before;

    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i =0; i< 100; i ++) {
            double v = (Math.random() * 10000) / 100;
            int a = (int)v;
//            System.out.println(a);
            list.add(a);
        }
        List<Integer> ilist =  qSort(list);
        for (Integer i : ilist) {
            System.out.println("输出：" + i);
        }
    }

}
